package com.sheng.leetcode.year2022.month07.day06;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author liusheng
 * @date 2022/07/06
 *
 * 736. Lisp 语法解析
 *
 * 给你一个类似 Lisp 语句的字符串表达式 expression，求出其计算结果。
 * 表达式语法如下所示:
 * 表达式可以为整数，let 表达式，add 表达式，mult 表达式，或赋值的变量。表达式的结果总是一个整数。
 * (整数可以是正整数、负整数、0)
 * let 表达式采用 "(let v1 e1 v2 e2 ... vn en expr)" 的形式，
 * 其中 let 总是以字符串 "let"来表示，接下来会跟随一对或多对交替的变量和表达式，
 * 也就是说，第一个变量 v1被分配为表达式 e1 的值，第二个变量 v2 被分配为表达式 e2 的值，
 * 依次类推；最终 let 表达式的值为 expr表达式的值。
 * add 表达式表示为 "(add e1 e2)" ，其中 add 总是以字符串 "add" 来表示，
 * 该表达式总是包含两个表达式 e1、e2 ，最终结果是 e1 表达式的值与 e2 表达式的值之 和 。
 * mult 表达式表示为 "(mult e1 e2)" ，其中 mult 总是以字符串 "mult" 表示，
 * 该表达式总是包含两个表达式 e1、e2，最终结果是 e1 表达式的值与 e2 表达式的值之 积 。
 * 在该题目中，变量名以小写字符开始，之后跟随 0 个或多个小写字符或数字。
 * 为了方便，"add" ，"let" ，"mult" 会被定义为 "关键字" ，不会用作变量名。
 * 最后，要说一下作用域的概念。计算变量名所对应的表达式时，
 * 在计算上下文中，首先检查最内层作用域（按括号计），
 * 然后按顺序依次检查外部作用域。
 * 测试用例中每一个表达式都是合法的。有关作用域的更多详细信息，请参阅示例。
 *
 * 示例 1：
 * 输入：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
 *
 *
 * 解：
 * 首先计算add x y
 * 通过let x 3 y 4，可大概理解为let x = 3, y = 4，那么add x y，可理解为x + y = 7
 * 那么可得(let x 3 y 4 (add x y))表达式的值为12，那么原表达式可变为(let x 2 (mult x 7))
 * 然后来计算mult x 7
 * 通过let x 2，可大概理解当前x的值为2，则mult x 7可理解为x * 7 = 14
 * 最后的出来的答案为14
 *
 *
 * 输出：14
 * 解释：
 * 计算表达式 (add x y), 在检查变量 x 值时，
 * 在变量的上下文中由最内层作用域依次向外检查。
 * 首先找到 x = 3, 所以此处的 x 值是 3 。
 *
 * 示例 2：
 * 输入：expression = "(let x 3 x 2 x)"
 *
 *
 * 解：
 * 首先x = 3，表达式变为let x 2 x
 * 然后x = 2，表达式变为x，求x的值
 * 最后的出来的答案为2
 *
 *
 * 输出：2
 * 解释：let 语句中的赋值运算按顺序处理即可。
 *
 * 示例 3：
 * 输入：expression = "(let x 1 y 2 x (add x y) (add x y))"
 *
 *
 * 解：
 * 第一个add x y，let x 1 y 2，可得x + y = 1 + 2 = 3
 * 此时原表达式变成了(let y 2 x 3 (add x y))
 * 再次计算add x y，let y 2 x 3，可得x + y = 3 + 2 = 5
 * 最后的出来的答案为5
 *
 *
 * 输出：5
 * 解释：
 * 第一个 (add x y) 计算结果是 3，并且将此值赋给了 x 。
 * 第二个 (add x y) 计算结果是 3 + 2 = 5 。
 *  
 * 提示：
 *
 * 1 <= expression.length <= 2000
 * exprssion 中不含前导和尾随空格
 * expressoin 中的不同部分（token）之间用单个空格进行分隔
 * 答案和所有中间计算结果都符合 32-bit 整数范围
 * 测试用例中的表达式均为合法的且最终结果为整数
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/parse-lisp-expression
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0736 {

    @Test
    public void test01(){
        String expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))";
//        String expression = "(let x 3 x 2 x)";
//        String expression = "(let x 1 y 2 x (add x y) (add x y))";
        System.out.println(new Solution().evaluate(expression));
    }

}
//class Solution {
//    public int evaluate(String expression) {
//        return 0;
//    }
//}

//今天身体不舒服，不写太详细，题目不难，大家结合代码看吧。
//设计函数 int dfs(int l, int r, Map<String, Integer> map) 函数，
//代表计算 s[l...r] 的结果，答案为 dfs(0,n-1,map)，其中 n 为字符串的长度。
//根据传入的 [l, r] 是否为表达式分情况讨论：
//若 s[l] = (，说明是表达式，此时从 l 开始往后取，取到空格为止（假设位置为 idx），
//从而得到操作 op（其中 op 为 let、add 或 mult 三者之一），
//此时 op 对应参数为 [idx + 1, r - 1]，也就是需要跳过位置 r（即跳过 op 对应的 ) 符号）；
//再根据 op 为何种操作进一步处理，我们设计一个「传入左端点找右端点」的函数 int getRight(int left, int end)，
//含义为从 left 出发，一直往右找（不超过 end），直到取得合法的「子表达式」或「对应的值」。
//对于 getRight 函数作用，给大家举个 🌰 理解吧，其实就是从 left 出发，找到合法的「子表达式」或「值」为止
// (let x 2 (mult x (let x 3 y 4 (add x y))))
//          a                               b
// 传入 a 返回 b，代表 [a, b) 表达式为 (mult x (let x 3 y 4 (add x y)))
//
// (let x 2 (mult x (let x 3 y 4 (add x y))))
//      ab
// 传入 a 返回 b，代表 [a, b) 表达式为 x
//否则 s[l...r] 不是表达式，通过判断 s[l...r] 是否有被哈希表记录来得知结果：若在哈希表中有记录，结果为哈希表中的映射值，否则结果为本身所代表的数值。
//需要注意，根据「作用域」的定义，我们不能使用全局哈希表，而要在每一层递归时，传入 clone 出来的 map。
//
class Solution {
    //cs为传入字符串的char数组
    char[] cs;
    //s为传入字符串
    String s;
    public int evaluate(String _s) {
        s = _s;
        cs = s.toCharArray();
        return dfs(0, cs.length - 1, new HashMap<>());
    }

    /**
     *
     * @param l 字符串的左端点
     * @param r 字符串的右端点
     * @param map 用于存放什么东西的map集合
     * @return 返回当前字符串计算后得到的值
     */
    int dfs(int l, int r, Map<String, Integer> map) {
        //如果当前字符串的第一个元素为'('时
        if (cs[l] == '(') {
            //将l赋值给idx
            int idx = l;
            //循环，找到第一个空格所在的位置
            while (cs[idx] != ' ') {
                idx++;
            }
            //此时op为单词let/mult/add其中之一
            String op = s.substring(l + 1, idx);
            r--;
            // 判别为 "(let"、"(add" 或 "(mult" 后，跳过对应的 ")"
            if (op.equals("let")) {
                //如果op为let时，i是let后面空格的后一位字符，一直循环到当前字符串结束
                for (int i = idx + 1; i <= r; ) {
                    //从i空格开始，到j位置又是一个空格，或者找到一个括号括起来的表达式
                    int j = getRight(i, r);
                    //key就是两个空格i和j之间的字符串
                    String key = s.substring(i, j);
                    //当满足判断式时，即找到的是一个括号括起来的表达式，对当前表达式继续进行循环
                    if (j >= r) {
                        return dfs(i, j - 1, new HashMap<>(map));
                    }
                    //将找到的右端点自增1后，赋值给左端点i
                    j++; i = j;
                    //然后继续找到下一个右端点，赋值给j
                    j = getRight(i, r);
                    int value = dfs(i, j - 1, new HashMap<>(map));
                    //比方说，此时key为x，value为2
                    map.put(key, value);
                    //将找到的右端点加1赋值给左端点i，然后再次循环
                    i = j + 1;
                }
                // never
                return -1;
            } else if (op.equals("add")) {
                //如果op为add时，将add左右的两部分分别计算出来并相加返回
                int j = getRight(idx + 1, r);
                int a = dfs(idx + 1, j - 1, new HashMap<>(map)), b = dfs(j + 1, r, new HashMap<>(map));
                return a + b;
            } else {
                //如果op为mult时，将mult左右两部分分别计算出来并相乘返回
                int j = getRight(idx + 1, r);
                int a = dfs(idx + 1, j - 1, new HashMap<>(map)), b = dfs(j + 1, r, new HashMap<>(map));
                return a * b;
            }
        } else {
            //当左端点不是括号时，走到当前位置，cur代表字符或者数字
            String cur = s.substring(l, r + 1);
            //如果当前cur作为key在map中出现过，则直接获取缓存（一般是字符）
            if (map.containsKey(cur)) {
                return map.get(cur);
            }
            //没有出现过（一般为数字），则将cur作为Integer返回
            return Integer.parseInt(cur);
        }
    }

    /**
     * 获取左端点找到右端点，如果左端点为'('，则找到对应的右括号，如果找到的不是左括号，而是空格，则返回两个空格之前的字符串（左端点左边一定也是空格）
     * @param left
     * @param end
     * @return
     */
    int getRight(int left, int end) {
        int right = left, score = 0;
        while (right <= end) {
            if (cs[right] == '(') {
                score++; right++;
            } else if (cs[right] == ')') {
                score--; right++;
            } else if (cs[right] == ' ') {
                if (score == 0) {
                    break;
                }
                right++;
            } else {
                right++;
            }
        }
        return right;
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/parse-lisp-expression/solution/by-ac_oier-i7w1/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
